#include <dbg.h>
#include <gtest/gtest.h>

#include <unordered_set>
using namespace std;

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        unordered_set<int> visited;
        dfs(rooms, 0, visited);
        return visited.size() == rooms.size();
    }

private:
    void dfs(vector<vector<int>>& rooms,
             int roomNum,
             unordered_set<int>& visited) {
        visited.insert(roomNum);              // 标记当前房间为已访问
        for (int keyNum : rooms[roomNum]) {   // 遍历当前房间的钥匙
            if (!visited.count(keyNum)) {     // 如果钥匙对应的房间未被访问过
                dfs(rooms, keyNum, visited);  // 递归访问钥匙对应的房间
            }
        }
    }
};

TEST(TEST1, allPathsSourceTarget) {
    Solution s;

    vector<vector<int>> rooms{{1}, {2}, {3}, {}};
    EXPECT_EQ(s.canVisitAllRooms(rooms), true);
}

TEST(TEST2, allPathsSourceTarget) {
    Solution s;

    vector<vector<int>> rooms{{1, 3}, {3, 0, 1}, {2}, {0}};
    EXPECT_EQ(s.canVisitAllRooms(rooms), false);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}